public class JumpGame {
    /*
    * 55. 跳跃游戏
    * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
    * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
    * 判断你是否能够到达最后一个下标。
    *
    * 1 <= nums.length <= 3 * 10^4
    * 0 <= nums[i] <= 10^5
    * */
    public static void main(String[] args){

    }

    // 我的想法：每次在可跳跃的范围内找能跳得最远的，看最后可跳跃长度是否能够超过数组长度
    // 结果是超时，确实低效
    public boolean mySolution(int[] nums){
        int start = 0;
        while (start < nums.length){
            int max = start;
            for (int i = start+1; i < nums.length && i <= start + nums[start]; i++) {
                int s = i + nums[i];
                if(s > max){
                    start = i;
                    max = s;
                }
            }
            if(max >= nums.length-1)
                return true;
        }
        return false;
    }

    // 没必要真搁那去跳
    // 一路加过来，用一个维护当前可到达最远位置，每走过一个格子就更新这个最远位置，看这个最终能不能超过数组长度
    // 时间复杂度为O(n)
    public boolean mySolution2(int[] nums){
        int farther = 0;
        for (int i = 0; i < nums.length; i++) {
            if(farther >= nums.length-1)
                return true;
            if(farther >= i){
                farther = Math.max(i+nums[i], farther);
            }
            else {
                return false;
            }
        }
        return false;
    }
}
